package utils

import "sort"

func binarySearch[T any](a []T, fromIndex, toIndex int, key T, comparse func(a, b T) int) int {
	low := fromIndex
	high := toIndex - 1

	for low <= high {
		mid := (low + high) >> 1

		midVal := a[mid]
		cmp := comparse(midVal, key)

		if cmp < 0 {
			low = mid + 1
		} else if cmp > 0 {
			high = mid - 1
		} else {
			return mid
		}
	}
	return -(low + 1)
}

// BinarySearch 使用二进制搜索算法在指定长度的数组中搜索指定的值,在进行此方法调用之前,须对数组进行排序(通过sort)方法,
// 如果未进行排序,则结果未定义。如果数组中包含多个具有指定值的元素,则无法保证会找到那一个元素所在的位置
// 如果未找到元素那么此结果必定小于0
// comparse方法需手动编写, string中存在默认的方法 strings.Comparse
// 此方法返回一个由开发者指定比较的顺序整数
// 如 a == b return 0
// a < b return -1
// a > b return +1
func BinarySearch[T any](a []T, key T, comparse func(a, b T) int) int {
	// fmt.Printf("val %v key %v \n", a, key)
	return binarySearch(a, 0, len(a), key, comparse)
}

// StringSort 字符串结构体排序
func StringSort(vals ...string) []string {
	cp := vals
	sort.Strings(vals)
	return cp
}
